#include <vector>

using namespace std;

// 尽量减少恶意软件的传播 II
// 给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示
// 在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
// 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，
// 且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
// 这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
// 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
// 我们可以从 initial 中删除一个节点，
// 并完全移除该节点以及从该节点到任何其他节点的任何连接。
// 请返回移除后能够使 M(initial) 最小化的节点。
// 如果有多个节点满足条件，返回索引 最小的节点 。
// initial 中每个整数都不同
// 测试链接 : https://leetcode.cn/problems/minimize-malware-spread-ii/

class Solution 
{
private:
    // 如果测试数据变大，就改变这个值
    static const int MAXN = 301;

    // initial : [3,6,103]
	// virus[3] = true;
	// virus[103] = true;
	// 方便查询
    // 方便查询
    bool virus[MAXN];
    // 每个源头点删掉的话，能拯救多少点的数据
    int cnt[MAXN];

	// 集合的标签 : 集合的感染点是什么点
	// a : 代表点，整个集合源头是 infect[a]
	// infect[a] == -1，目前这个集合没有发现源头
	// infect[a] >= 0，目前这个集合源头是 infect[a]
	// infect[a] == -2，目前这个集合源头不止一个，已经无法拯救了!
    int infect[MAXN];

    // 并查集固有信息
    int father[MAXN];

    // 集合的标签 : 集合的大小是多少
    int size[MAXN];

    // 集合一定只放普通点，源头点根本不参与集合，也不是元素！

    void Build(int n, vector<int>& initial)
    {
        for(int i = 0; i < n; ++i)
        {
            virus[i] = false;
            infect[i] = -1;
            cnt[i] = 0;
            father[i] = i;
            size[i] = 1;
        }

        for(int i : initial)
        {
            virus[i] = true;
        }
    }

    int Find(int i)
    {
        return i == father[i] ? i : father[i] = Find(father[i]);
    }

    void Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy)
        {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }

public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) 
    {
        int n = graph.size();
        Build(n, initial);
        // 不是病毒的点，普通点合并！
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(graph[i][j] == 1 && !virus[i] && !virus[j])
                {
                    Union(i, j);
                }
            }
        }

        // 病毒周围的普通点(集合)去设置源头！
        for(int sick : initial)
        {
            for(int neighbor = 0; neighbor < n; ++neighbor)
            {
                if(sick != neighbor && !virus[neighbor] && graph[sick][neighbor] == 1)
                {
                    int fn = Find(neighbor);
                    if(infect[fn] == -1)
                    {
                        infect[fn] = sick;
                    }
                    else if(infect[fn] != -2 && infect[fn] != sick)
                    {
                        infect[fn] = -2;
                    }
                }
            }
        }

        // 统计拯救数据
        for(int i = 0; i < n; ++i)
        {
            // 不是代表点不看
            if(i == Find(i) && infect[i] >= 0)
            {
                cnt[infect[i]] += size[i]; // 删除该源点，拯救普通点的个数
            }
        }

        // 将源头点按照大小进行排序
        sort(initial.begin(), initial.end());
        int ans = initial[0], max = cnt[ans];
        for(int i : initial)
        {
            if(cnt[i] > max)
            {
                max = cnt[i];
                ans = i;
            }
        }
        return ans;
    }
};